The present invention is directed to a system and method for reducing hybrid error diffusion pattern shifting at certain grey levels and is dependent upon the image processing operations associated with the pixel being processed. More specifically, the present invention is directed to providing a dynamic noise profile to reduce hybrid error diffusion pattern shifting at certain grey levels by perturbing the threshold value used to binarize the image data wherein the noise profile is selected based on a window effect pointer or image classification of the pixel being processed and/or the grey level of the pixel being processed.
There are many methods of rendering grey images on an output device. One such example is error diffusion. Error diffusion can render complex images that contain a mixture of text and picture reasonably well. The utilization of error diffusion eliminates the need to have image segmentation to separate the text from the picture so that the picture aspect of the document can be screened and the text aspect of the document can be threshold.
FIG. 1 illustrates a flowchart of a typical error diffusion binarizafion system. In Step S1 of this process, the video signal for pixel X is modified to include the accumulated error diffused to this pixel from previous threshold processes. The modified video signal value X is compared at Step S2 with the value 128, assuming a video range between 0 and 255. If Step S2 determines that the modified video signal value X is greater than or equal to 128, the process proceeds to Step S4 wherein a value is output to indicate the turning ON of pixel X. The process then proceeds to calculate the error associated with the threshold process at Step S6 wherein this error, Y, is calculate as being Xxe2x88x92255.
On the other hand, if Step S2 determines that the modified video signal value X is less than 128, a signal is output at Step S3 indicating that the pixel X is to be turned OFF. The process then proceeds to Step S5 wherein the error, Y, is calculated as being equal to the value X.
The error calculated in either Steps S5 or S6 is multiplied by weighting coefficients and distributed to downstream pixels in Step S7. Thus, the error from the threshold process is diffused to adjacent pixels. The coefficients conventionally used to diffuse the error to adjacent downstream pixels.
In addition to the typical error diffusion described above, hybrid high addressability error diffusion process can also be utilized which will be explained briefly.
Typically, the image processing architecture of a printing system uses either the functions of screening, thresholding, or error diffusion. For pixels to be screened, a similar modified video signal, VSxe2x80x2, is computed from the pixel video signal V and the screen value S at the pixel location. The modified video signal, VSxe2x80x2, for a conventional screening process is defined as VSxe2x80x2=(S+255xe2x88x92V)/2 in a system having 256 grey levels. The screen value S depends on the pixel location as well as the halftone screening pattern being used. It is noted that either a line screen or a dot screen can be used.
In the final step of binarization, the modified video signal, VSxe2x80x2, is compared with 128 to determine the ON or OFF characteristics of the pixel. Namely, if the modified video signal is greater than or equal to 128, the pixel should be OFF (black), otherwise it should be ON (white). FIG. 2 illustrates a typical circuit for carrying the screening process wherein a screen value is added to the video signal by modulator 1 and comparator 3 compares the modified video signal with the threshold value. It is noted that this example gives the same result as the more typical approach of comparing the video V itself with a screen in lieu of the threshold value.
Hybrid error diffusion is the intertwining of the typical screening process with conventional error diffusion. Moreover, the typical error diffusion process can be extended to a high addressability environment. The blending of these three process will be discussed in more detail below.
To extend the conventional error diffusion process, described above, to a hybrid high addressability environment, the binarization (threshold) is performed at a higher spatial resolution, but the error computation and propagation is performed at the original lower spatial resolution. This splitting of the process substantially prevents or reduces the number of isolated subpixels, thereby maintaining high image quality.
In explaining the hybrid high addressability error diffusion process, it is assumed that the input grey levels at pixel location i and pixel location i+1 are represented by Vi and Vi+1, respectively, wherein Vixe2x80x2=(GLxe2x88x92Vi)+(Sixe2x88x92Th), and Vi+1xe2x80x2=(GLxe2x88x92Vi+1)+(Sii+1xe2x88x92Th) wherein GL is the maximum grey level a pixel can have, Si and Si+1 are the screen values for the pixels based on position of the pixels, and Th is the threshold value. The rendering error, at the lower resolution, that passes from upstream pixels to the downstream pixel location is denoted by ei.
It is noted that a feature of high addressability involves interpolation between pixels, the creation of subpixels. This interpolation impacts the hybrid high addressability error diffusion process. More specifically, depending on the way the interpolation is done, two distinct outputs can be obtained utilizing the high addressability error diffusion process. Each one of these distinct outputs will be discussed below.
With respect to a first interpolation scheme, the steps for determining the printing or rendering of a subpixel are as follows.
Initially, the modified pixel values P0i=Vi+ei and P1i=Vi+l+ei are computed wherein Vixe2x80x2=(GLxe2x88x92Vi)+(Sixe2x88x92Th), and Vi+1xe2x80x2=(GLxe2x88x92Vi+1)+(Si+1xe2x88x92Th). The subpixels are denoted by 0 to Nxe2x88x921 wherein the high addressability characteristic is N. The high addressability characteristics is the number of subpixels that a printer can produce compared to the throughput bandwidth of the image processing system. In other words, the high addressability characteristic defined as the number of subpixels that the image output terminal can render from one pixel of image data.
High addressability is important in situations where the device can process the image data at one resolution, but print at a higher resolution. In such a situation, the present invention can take advantage of a processing system designed for a lower resolution image, (lower resolution can be processed quicker and less expensively), and a printing device which, through laser pulse manipulation, can print at a higher resolution. For example, the image can be processed at 600xc3x97600xc3x978 and printed at 2400xc3x97600xc3x971 using the high addressability process. In the above example, the high addressability characteristic is 4. If the image was processed at 600xc3x97600xc3x978 and printed at 1200xc3x97600xc3x971, the high addressability characteristic would be 2.
The interpolated subpixel values are computed as Bn=P0+n(P1xe2x88x92P0)/N for n=0 to Nxe2x88x921. The interpolated subpixel values are then compared with a threshold value which in most cases is 128, assuming that the video value ranges from 0 to 255 (GL is equal to 255). If Bn is greater than or equal to 128, the subpixel is turned ON; otherwise, the subpixel is turned OFF. The error to be propagated to downstream pixels is computed as the desired output, (P0+P1)/2, minus the actual output, namely, y*255/N, wherein y is the number of subpixels turned ON. The error is then multiplied by a set of weighting coefficients and distributed to the downstream pixels as in the first version.
More specifically, the screened inputted modified video signal is divided into N subpixel units. The P0 and P1 values are computed as noted above. The computed subpixel values are compared with a threshold value, namely 128. If the subpixel value is greater than or equal to the threshold value, the subpixel value is set to the ON state. However, if the subpixel value is less than 128, the subpixel value is set to the OFF state.
Upon completing the comparison of all subpixel values, the number of ON subpixels are calculated. Moreover, the error from the threshold process is calculated so that the value represents the original lower spatial resolution. Upon calculating the error, the error is multiplied by weighting coefficients and distributed the error to downstream pixels.
As noted above, the modified pixel values P0i=Vixe2x88x921+eixe2x88x921=P1ixe2x88x921 and P1i=Vi+ei are computed at two locations corresponding to the input resolution wherein Vi=(GLxe2x88x92Vi)+(Sixe2x88x92Th) and Vixe2x88x921=(GLxe2x88x92Vixe2x88x921)+(Sixe2x88x921Th). An example of this is illustrated in FIG. 17 wherein the subpixels are denoted by 0 to Nxe2x88x921. In FIG. 17, the high addressability characteristic, N, is equal to 4.
As illustrated in FIG. 16, a line is drawn to connect the values P0 and P1. (The i subscripts have been dropped for simplicity.) Moreover, a dotted line is drawn to represent a threshold value of 128. (Again, it is noted that 0 to 255 is the range of the video signal; however, any range can be utilized and any threshold value may be used.) The intersection of the line connecting P0 and P1 and the line representing the threshold at 128 determines which subpixels are to be rendered or printed. The X coordinate of the point of intersection is determined and normalized to N by the equation X=N(128xe2x88x92P0)/(P1xe2x88x92P0).
Next, it is determined which subpixels are to be turned ON. If X is less than or equal to 0 and if P1 is greater than or equal to 128, all the subpixels are ON; otherwise, all the subpixels are OFF. This decision represents the complete rendering or non-rendering of the pixel. To determine a partial rendering of the whole pixel, a subpixel analysis must be performed. In this instance, the value X must be compared to the individual subpixel values.
It is noted, as illustrated in FIG. 16, that the value of X does not necessarily compute to a whole number or subpixel, thereby making any analysis include a fractional component. To avoid this, X is converted to a whole number or subpixel value as illustrated in FIG. 17. For this conversion, n is allowed to be equal to the truncated integer value of X. The values n and X can then be utilized to determine which subpixels are to be turned ON and which subpixels are to be turned OFF. More specifically, if X is greater than 0, but less than n, and if P1 is less than 128, only the subpixels from 0 to n are turned ON and the rest of the subpixels are turned OFF; otherwise, the subpixels from 0 to n are turned OFF and the rest are turned ON. If X is greater than or equal to n and if P0 is greater than or equal to 128, all subpixels are turned ON; otherwise, all subpixels are turned OFF.
This threshold process produces an error which needs to be propagated to downstream pixels. Moreover, as noted above, the error needs to be at the original low resolution input. The conversion to the original resolution is realized by determining the difference between the desired output, (P0+P1)/2, and the actual output, namely b*255/N where b is the number of subpixels that were turned ON. The converted error is then multiplied by a set of weighting coefficients and distributed to the downstream pixels.
The second interpolation method, with respect to implementing the hybrid high addressability error diffusion method, is the same as the first implementation except the modified pixel values in the second implementation are calculated as follows P0i=Vi+ei and P1i=Vi+1+ei wherein Vi=(GLxe2x88x92Vi)+(Sixe2x88x92Th) and Vixe2x88x921=(GLxe2x88x92Vixe2x88x921)+(Sixe2x88x921xe2x88x92Th). The difference in the implementations can be seen in FIGS. 18 and 19.
FIG. 18 illustrates the high addressability relationship between adjacent pixels utilizing the first interpolation version of high addressability error diffusion method. More specifically, it is noted that the P1 value of the present pixel is utilized as the P0 value for the next pixel.
On the other hand, FIG. 19 illustrates the high addressability relationship between pixels utilizing the second interpolation version of the high addressability error diffusion method. In this case, there is discontinuity between the P1 value of the previous pixel and the P0 value of the present pixel. Thus, from these two Figures, it can be seen that the error output from the two versions of the hybrid high addressability error diffusion methods will be different.
One problem associated with the utilization of a typical error diffusion process or a hybrid high addressable error diffusion process in rendering an image on a document is the occurrence of periodically repeating patterns. These patterns occur most notably at the grey levels of 85, 128, and 170 when an 8 bit data word is utilized to represent the grey level of the image data. For example, when the grey level input is 128, the binarized image can alternate between a checkerboard pattern and a vertical line pattern. Depending on the printer spot size and the grey level at which the spot was mapped, the vertical line pattern can appear lighter than the checkered board pattern, thereby producing a undesired artifact.
The idea of dithering or adding threshold perturbations to defeat visual artifacts of a regular and deterministic nature has been utilized in the prior art. For example, in the article xe2x80x9cDigital Halftoningxe2x80x9d by Robert Ulichney, it was proposed to add random noise, across the entire image, to the elements of the error weights or to the threshold to defeat the visual artifacts discussed above. However, by adding noise to all parts of an image tends to degrade the image and will also destroy the dot pattern established in the highlight and shadow areas.
Therefore, it is desirable to perturb only the threshold in those areas where the occurrence of periodically repeating patterns are distracting. More specifically, it is desirable to eliminate pattern shifting artifacts by making one of the patterns much less likely to occur. On the other hand, it is desirable to mask this artifact by making the transitions between the patterns happen more frequently, thereby breaking up the regular patterns.
A first aspect of the present invention is a system for reducing a number of levels in a multi-level grey scale pixel value representing a pixel and diffusing an error generated from reducing the number of levels. The system includes means for receiving a multi-level grey scale pixel value representing a pixel having a first resolution. Reduction means reduces the number of levels in the multi-level grey scale pixel value; error means generates an error value as a result of the reduction process by said reduction means; and diffusing means diffuses the error value to multi-level grey scale pixel values of adjacent pixels. Perturbing means perturbs the relationship between the threshold value and the multi-level grey signal according to an image classification of the multi-level grey signal, thereby effecting the output from the conversion means.
A second aspect of the present invention is a method of reducing a number of levels in a multi-level grey scale pixel value representing a pixel and diffusing an error generated from reducing the number of levels. The method receives a multi-level grey scale pixel value representing a pixel having a first resolution. The number of levels in the multi-level grey scale pixel value are reduced, generating an error value which is diffused to multi-level grey scale pixel values of adjacent pixels. The relationship between the threshold value and the multi-level grey signal is perturbed according to an image classification of the multi-level grey signal, thereby effecting the output.
Further objects and advantages of the present invention will become apparent from the following descriptions of the various embodiments and characteristic features of the present invention.